package everydayone.addTwoNumber;

import primaryAlgorithm.deleteNode.ListNode;

/**
 * @Date 2020/04/14
 * @author 王光浩
 * @Thinking 使用双指针方法，首先将指针移动到两个链表的末尾，然后进行相加，并判断是否需要进位。
 * @Analysis 时间复杂度O（n），空间复杂度O（n）
 */
public class MyMethodTwo {
	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		// 将 l1 进行翻转
		ListNode node1 = l1;
		ListNode ret1 = null;
		while (node1 != null) {
			ListNode tem = new ListNode(node1.val);
			tem.next = ret1;
			ret1 = tem;
			node1 = node1.next;
		}
		// 将 l2 进行翻转
		ListNode node2 = l2;
		ListNode ret2 = null;
		while (node2 != null) {
			ListNode tem = new ListNode(node2.val);
			tem.next = ret2;
			ret2 = tem;
			node2 = node2.next;
		}
		// 将数字进行合并
		node1 = ret1;
		node2 = ret2;
		ListNode ret = null;
		int overflow = 0;
		// 按节点进行相加
		while (node1 != null && node2 != null) {
			// 将两个节点相加的结果保存（注意溢出）
			int count = node1.val + node2.val + overflow;
			ListNode tem = new ListNode(count % 10);
			overflow = (count) >= 10 ? 1 : 0;
			tem.next = ret;
			ret = tem;
			// 进入下一个节点
			node1 = node1.next;
			node2 = node2.next;
		}
		if (node1 == null)
			while (node2 != null) {
				// 将 node2 的剩下节点加入 结果中（注意溢出）
				int count = node2.val + overflow;
				ListNode tem = new ListNode(count % 10);
				overflow = (count) >= 10 ? 1 : 0;
				tem.next = ret;
				ret = tem;

				node2 = node2.next;
			}
		if (node2 == null)
			while (node1 != null) {
				// 将 node2 的剩下节点加入 结果中（注意溢出）
				int count = node1.val + overflow;
				ListNode tem = new ListNode(count % 10);
				overflow = (count) >= 10 ? 1 : 0;
				tem.next = ret;
				ret = tem;

				node1 = node1.next;
			}
		if(overflow == 1) {
			ListNode tem = new ListNode(1);
			tem.next = ret;
			ret = tem;
		}
		return ret;
	}
}
